Consider the fraction, n/d, where n and d are positive integers. If n < d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 21 elements in this set.
How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?
In [1]:
N = 1000001
phi = [0] * N
phi[1] = 1
primefactor = [0] * N
for p in range(2, N):
if primefactor[p] == 0:
for n in range(p, N, p):
primefactor[n] = p
for n in range(2, N):
q = primefactor[n]
m = n // q
power = 1
while primefactor[m] == q:
m //= q
power *= q
phi[n] = phi[m] * power * (q-1)
print(sum(phi))
Explanation: The number of reduced fractions with denominator $n$ is $\phi(n)$ (Euler's totient function) so the answer is $\sum_{k \le 10^6} \phi(k)$.